package com.lun.easy;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class SumOfLeftLeaves {
	
	//方法一：递归法
    public int sumOfLeftLeaves(TreeNode root) {
    	if(root == null) return 0;
    	int temp = 0;
    	if(root.left != null && root.left.left == null && root.left.right == null)
    		temp = root.left.val;
    	
    	return temp + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
    
    //方法二：迭代法
    public int sumOfLeftLeaves2(TreeNode root) {
        if(root == null) return 0;
        int ans = 0;
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) {
                if (node.left.left == null && node.left.right == null)
                    ans += node.left.val;
                else
                    stack.push(node.left);
            }
            if(node.right != null) {
                if (node.right.left != null || node.right.right != null)
                    stack.push(node.right);
            }
        }
        return ans;
    }
    
}
